COMMENT ⊗   VALID 00010 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	folio 595 galley 1 NOTE: The next nine galleys were all pretty much lost.
C00021 00003	folio 595 galley 2
C00035 00004	folio 598 galley 3
C00036 00005	folio 600 galley 4
C00041 00006	folio 604 galley 5
C00044 00007	folio 609 galley 6
C00052 00008	folio 611 galley 7
C00068 00009	folio 614 galley 8
C00071 00010	folio 618 galley 9
C00077 ENDMK
C⊗;
folio 595 galley 1 NOTE: The next nine galleys were all pretty much lost.
    0  {U0}{H10L12M29}|πW58320#Computer|9Programming!ch. 
    1  4!f. 592!g. 1|'{A6}|εProof.|9|4|πWe may assume 
    7  that |εt|4|¬Q|42, |πsince the result of the theorem 
   15  is true without restriction on the |εe'|πs when 
   23  |εt|4|¬R|42. |πSuppose that we have a star chain 
   31  1|4α=↓|4|εa|β0|4|¬W|4a|β1|4|¬W|4|¬O|4|¬O|4|¬O|4|¬W|4a|βr|4α=
   31  ↓|4n |πfor |εn |πwith |εr|4|¬E|4e|β0|4α+↓|4t|4α_↓|41. 
   36  |πLet the integers |εd, f, d|β0,|4.|4.|4.|4,|4d|βr, 
   42  |πand the multisets |εM|βi|βj |πand |ε*3|βi |πrd&&ct 
   49  thesstrkkourdsof this chain, as de_ned earlier. 
   55  By the corollary to ThebrexnA≡,qaskfm∧qhhuw |\*2F44¬}S44[∩377
   60  77)H4↓↓45([∩\;|[πhyjjfxgjshhys Q*2m [7cnn7)iusiunbmkui≠dsiqpp
   62  drnboknd eakh mulliset |\(|βj*2[]][o!|::44555555Cnhhyssu¬m¬wp
   65  cmnN⊃{U6}\εuIiiI7(≡|4N↔uN≡k|kcN)xN¬JM|βi|β0N)2|gx|↔s|4α+↓|4|
   65  ↔a|↔k|uc|)x|¬AM|βi|β1|)↑6gx|↔sS4α+↓|44¬BN4|¬ON4|¬ON4α~↓*444↔≡
   65  U↔≡KUkC()F¬JMNβi|βt|)↑←gxF↔↔↔←;↓J**Kπ'nnmncjrciss 
   66  vgmpjgatenfrom the term corresponding to |εM|βi|βj 
   72  |[to thystervmcvgrjsqvmfkcvvhom|\MUkC(*2*2↓↓↓↓((),|[7kfqws 
   74  hpckknmf hhissukm usxbuccvckjrriddnout in the 
   79  binary nk¬bercsyszex,,succksthys|\ε-][(sujjssxmfkjcuqpjrm. 
   81  P≥3Cf.n(4π).I*26 In partccular, the sum of all 
   88  the terms fxg |εjK44*/←↔***241→|[↓qplpnmohckjrry 
   92  uphoo a=dct the terms for |εj|4α=↓|40, |πso we 
  100  must have|'|ε&a|βiI44¬}C44↔≡KukC)x|¬AXNβi|β0←)*454536V¬F44}¬C
  102  466UkC≤**UIi*2((((),!0→44}}S44i44}¬S46#[KJ(4):{**}[π!|9|4|1|1|1
  102  In order to prove Theorem H, wesqould like tonshow 
  111  that in some seffssthss|\εh|[αxxgjupv∧wjksmmfc6nvckkrccngicn
  114   hhenbcnjcynruvresdntatcon of |εn |πmusy be pqq 
  121  inn]`πnesuwhuuhpvf↔'' sbnqwsqakmhhom=≡ffa way 
  124  to tell at whicm syeqisakvhmxfhhyssshzjvxsssssfmpuwlpy 
  129  dntjcs tell at which step each of these terms 
  138  essentially enters the additionncmain.|'!|9|4|1|1|1Let 
  143  |εj |πbe a number between 1 and |εt. |πSince 
  152  |εM|β0|βj |πis empty and |εM|βr|βj|4α=↓|4M|βj 
  157  |πis nonempty, we can _nd the |ε⊂rst |πstep |εi 
  166  |πfor which |εM|βi|βj |πis not empty.|'!|9|4|1|1|1From 
  173  the way in which the |εM|βi|βj |πare de_ned, 
  181  we know thaz szeq |εi |πis a non-doubling; |εa|βi|4α=↓|4a|βi
  189  |βα_↓|β1|4α+↓|4a|βu |πfor some |εu|4|¬W|4i|4α_↓|41. 
  193  |πWe also know that all the elements of |εS|βu. 
  202  |πWe will prove that |εa|βu |πmust be relatively 
  210  small compared to |εa|βi.|'!|9|4|1|1|1|πLet |εx|βj 
  216  |πbe an element of |εM|βi|βj. |πThen since |εx|βj|4|¬A|4S|βu
  223  , |πthere is some |εv |πfor which |εx|βj|4|¬A|4M|βu|βv. 
  231  |πIt follows that|'{A6}|εd|βi|4α_↓|4d|βu|4|¬Q|4m,|J!(45)|;
  235  {A6}|π⊗i.e., at least |εm|4α+↓|41 |πdoublings 
  240  occur between steps |εu |πand |εi. |πFornif |εdSβi|4α_↓|4d|β
  247  uS4|¬E|4., |πLemma K tewlssussthaw |ε*/¬{dSβjF4α≠↓←4&SIvC¬}C4
  251  4}}Q467);|[[yfcks|\*2V44***2.|[α}qh hpis isicmpossible 
  254  because |εM|βu|βj |πis empty by our cvoccesmxfszeqi|≥=#[,'|:
  260  :4455P5P5[↓Wlpswwxxfmtsnof |εS|βu |πare less 
  264  than or equaw to |ε_Sβ1|4α~↓**4d|βiI4≠↓|4≠FIi#,|π(Xgcikf|≥*2X4
  268  4}}U4*/sIuu44*4)Y4*/SIii [↓kff I≤x|4|¬Q|4e|β1|4α+↓|4d|βi|4α_↓|4
  270  d, |πthen |εx|4|¬A|4M|βu|β0λ|[≠kff|≥*2X44¬}U47MIiII1→ 
  273  [αxy)5();sxm Lemma K implies that |¬G|εd|βi|4α_↓|4d|βu|¬G|4|
  278  ¬W|4m, |πconoradicoingc(5).ICnfkkv.,hhpisijg¬kmdnt 
  280  vroves that |εM|βi|β0 |πhas no elements inncommomnwith 
  287  |εS|βu,,|π?S|βu, |πso |εM|ur|)(iα_↓1)0|)|4α=↓|4M|βi|β0. 
  290  |πFrom (44) we have |εa|βi|βα_↓|β1|4|¬R|42|ur|≤l(a|βi)|)|), 
  295  |πand therefore |εstep i is a small step.|'!|9|4|1|1|1|πWe 
  304  can now deduce what is probably the key fact 
  313  in this entire proof: |εAll elements of S|βu 
  321  are in M|βu|β0. |πFor if not, let |εx |πbe an 
  331  element of |εS|βu |πwith |εx|4|=|↔6|¬A|4M|βu|β0. 
  336  |πSince |εx|4|¬R|40, |π(40) implies that |εe|β1|4|¬R|4d|4α_↓
  341  |4d|βu, |πhence|'{A6}|π|εe|β0|4|¬E|4r|4α=↓|4f|4α+↓|4d|4|¬E|4
  343  3.271(t|4α_↓|41)|4α+↓|4e|β1|4α+↓|4d|βu.|;{A6}|πBy 
  345  hypothesis (43), this implies |εd|βu|4|¬Q|4e|β1. 
  350  |πBut |εd|βu|4|¬A|4S|βu |πby (41), and it cannot 
  357  be in |εM|βi|β0, |πhence |\≤Fβu|4|¬DS4e|β1|4α+↓|4d|βi|4α≠↓N4
  361  dN4|¬D|4e|β1, |πa contradiction.|'!|9|4|1|1|1Going 
  365  back to our element |εx|βj |πin |εM|βi|βj, |πwe 
  373  have |εx|βj|4|¬A|4M|βu|βv; |πand we have provedfthat 
  379  |ε#|4α≡↓*440.,|ππhejjfxgj↔,xxysqquzignn(**0)↔a∧jun,]'{A6}F≥&e|
  379  β0←4α+↓←4-Fβu|4α_↓|4dF4|¬R|4x|βj|4|¬Q|4e|β0|4α+↓|4d|βu|4α_↓|
  379  4d|4α_↓|4m.|J!(44)|;{A6}|π!|9*34455145xgcuwlp|≥≤K4α*245#]42/]4
  380  #]4.]4#]4/]4∀ |π≤wshq¬ksfdzzjvvcfdfuunk¬xbjc|≥*2XIjk|[(uwpufx
  381  qcvv(4*2),ukffuusx¬wlpsyzqp \≥i [↓whiqpcchn(in 
  384  fome sense) the term |ε2|ure|βj|)|) |πin |εn 
  391  |πhas entejddficoonthysujdkppvmncvquc..IKf≠|\≤K44*/*/*4≡*24**kC¬F
  392  , Nπthe step |εi |πat which thiu occujkscannoo 
  400  be thyssu¬xsfxgcxbohh|\≤k M↓knf |≤kN¬S; |πfor 
  405  (44) would tell us that |ε*3¬{x|βj|4↓≠↓|4xFUkC)≠S¬KS((}}V44}}
  410  Q47.,|[↓qppwsswwfxfmhsnmf |εM|βi|βj |πand |εM|ur|)ij|¬S|(?|π
  413  musz diεM|ur|)ij|¬S|) |πmust di=er by more than 
  420  |εm, |πsince |εe|βj |πand |εe|ur|)j|¬S|) |πare 
  426  so far apart. Therefore the chain contains at 
  434  least |εt |πsmall steps, but this is a contradiction.|'
  443  |'|≡T|≡h|≡e|≡o|≡r|≡e|≡m |≡F (W. Hansen).|'{A6}|εl(2|gA|4α+↓|
  448  4xy)|4|¬E|4A|4α+↓|4|≤n(x)|4α+↓|4|≤n(y)|4α_↓|41,!!|πif!!|ε|≤l
  448  (x)|4α+↓|4|≤l(y)|4|¬E|4A.|J!(45)|;{A6}|π|εProof.|9|4|πAn 
  450  addition chain (which is |εnot |πa star chain 
  458  in general) may be constructed by combining the 
  466  binary method and the factor method. Let |εx|4α=↓|42|gx|r1|4
  473  α+↓|4|¬O|4|¬O|4|¬O|4α+↓|42|gx|ru, y|4α=↓|42|gy|r1|4α+↓|4|¬O|
  474  4|¬O|4|¬O|4α+↓|42|gy|rv, |πwhere |εx|β1|4|¬Q|4|¬O|4|¬O|4|¬O|
  476  4|¬Q|4x|βu|4|¬R|40, y|β1|4|¬Q|4|¬O|4|¬O|4|¬O|4|¬Q|4y|βv|4|¬R
  477  |40.|'!|9|4|1|1|1|πThe _rst stepssof theschain 
  482  form sukcessuvjspgwerfsof 2, ufoil 2←gA|gα_↓|gy|r1 
  487  is reached; in between these steps, thesvaluess|ε2|gxFru|rα≠
  493  ↓*4r1←4α+↓|426gxFru↔,66vxXrkSrα≠↓*4r2]4α~↓*442]gxXrkScα≤↓*4r3←4α
  493  ~↓*4426v¬Xck≡]4#[4#[4#[4/,|[≠kff|ε)x|[≤jjsicfsjgzdficnhhysuqp
  493  vgvvcuwzsppwkks).UKxzjcuucvqucnuqphom Q≤6NgANgα≠↓|gy|ri|4α+↓
  494  |4x(2|gy|r1| the appropriate places. After a 
  499  chain up to |ε2|gA|gα_↓|gy|ri|4α+↓|4x(2|gy|r1|gα_↓|gy|ri|4α+
  502  ↓|4|¬O|4|¬O|4|¬O|4α+↓|42|gy|ri|rα_↓|r1|gα_↓|gy|ri) 
  503  |πhas been formed, continue by adding |εx |πand 
  511  doubling the latter result |εy|βi|4α_↓|4y|βi|βα+↓|β1 
  516  |πtimes; this yields|'{A6}|ε2|gA|gα_↓|gy|ri|rα+↓|r1|4α+↓|4x(
  519  2|gy|r1|gα_↓|gy|ri|rα+↓|r1|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|42|ury|β
  519  iα_↓y|βi|βα+↓|β1|)|)).|;{A6}|πIf this construction 
  523  is done for |εi|4α=↓|41,|42,|4.|4.|4.|4,|4v, 
  527  |πassuming for convenience that |εy|βv|βα+↓|β1|4α=↓|40, 
  532  |πwe have an addition chain for |ε2|gA|4α+↓|4xy 
  539  |πas desired.|'|'!|9|4|1|1|1|πTheorem F enables 
  545  us to _nd values of |εn |πfor qqpch |εl(n)|4|¬W|4l|≤⊂(n), 
  554  |πsince Theorem H givds an ex¬licit value of 
  562  |εl|≤⊂(↔)?|πinncdjoaic cases),For example, let 
  566  |εx|4α=↓|42|g1|g0|g1|g6|4α+↓←41,λy|4α=↓|42←g2|g0|g3|g2←4α+↓|
  566  41, |πafdflez |εn|4α≡↓|42|g6|g1|g0|g6|4α+↓|4xy|4α=↓|42|g6|g1
  568  |g0|g6|4α+↓|42|g3|g0|g4|g8|4α+↓|42|g2|gπ|g3|g2←4α+↓|42]g3←g3
  568  ←g14g664α∃↓|41#,|But Theorem H also aqplies↔,quth 
  573  |εm|4α=↓|4508, |πand this proves that |εl|≤⊂(n)|4α=↓|46110.|
  578  '|π!|9|4|1|1|1Extensive computer calculations 
  582  have shown that |εn|4α=↓|412509 |πis the smallest 
  589  value with |εl(n)|4|¬W|4l|≤⊂(n). |πNo star chain 
  595  for this value of |εn |πis as short as the sequence 
  606  1, 2, 4, 8, 16, 17, 32, 64, 128, 256, 512, 1024, 
  618  1041, 2082, 4164, 8328, 8345, 12509) The brute 
  626  force mezhodsin thesprgoffof ThebrjxnCccvkqdfxbssxxeffddfxxy
  629  cvmvqqzjcpvgggj¬nhomfdzzjvvcfsuwlp|\*2nsukvhhhqwh|\ε()(4*244≤¬
  629  (n)|6α∩|43; Nπthis approach would also characterize 
  635  all |εn |πwith |ε|≤n(n)|4α=↓|45λ|πand |εl(,)*444=*/*4***2↓45P*2≤))
  639  ).(([πHsssx¬wlwsyhsukvh|≥*2n|[7us5777774*2466V35V#44α↓I4:I4K¬M
  639  I437.)|'|'|≡S|≡o|≡m|≡es|≡c|≡o|≡,|≡j|≡&S≡c|≡≤|**≡U≡≡C≡≡S**≡S***2[
  641  ::4*/Wlhm¬¬vhiphqwuscjaafmkj∧le to guess at _rst 
  646  glance that |εl(n)*44α=↓|4l|≤⊂(n), |πweshu¬ksnm∧qssefnhhqah 
  650  hhusiis false. Another plausible conjecture [_rst 
  656  majd by A.λGoulard↔,andssuqpvxsd∧qy,`7vgv¬dd',nxy 
  659  E.nde Jonqui|=2eres in |εl'IIIIICICICICCCCCCccnnnnnnnnnnnnnn
  662  nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn
  662  nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn
  662  nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn
  662  nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn
  662  nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn
  662  nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn
  662  nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn
  662  nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn
  662  nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn
  662  nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn
  662  nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn
  662  nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn
  662  nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn
  662  nnnnnnnnnnnnnnnnnnnnnnnnnnni*?*?d,,and suqposedwy 
  664  ``proved''nbx E. ddsJonqui|=2eres in |εl'Interm. 
  669  des Math. |π|≡2 (1895), 125<126] is that |εl(2n)|4α=↓|4l(n)|
  676  4α+↓|41; |πa doubling step is so e∃cient, it 
  684  seems unlikely that there could be any shorter 
  692  chain for |ε2n |πthan to add a doubling step 
  701  to the shortest chain for |εn. |πBut computer 
  709  calculatiofymqsthat this conjecture also fails, 
  714  since |εl(191)|4α=↓|4l(382)|4α=↓|411. (A star 
  718  chain of length 11 for 382 is not hard to _nd; 
  729  e.g., 1, 2, 4, 5, 9, 14, 23, 46, 92, 184, 198, 
  741  382. |πThe number 191 is minimal such that |εl(n)|4α=↓|411, 
  750  |πand it seems to be very di∃cult to provd bxshakffhhqt 
  760  |εl(*5*5*2(4|¬}Q450;y|["hsscvmvqqzj⊃↔spvgoxfmxfhhpusfkkv.,uuucv
  760  vuux∧kk¬gjkkkmmehmofuqhich will be sketched in 
  765  Section 7.2.2, involved a detailednsxaminjwivnnmff:\*/*3ckuss)
  769  ))HHyssx¬wlwsshfxmkrnvalues of |εn |πsuch that 
  774  |εl(2n)|4α=↓|4l(n) |πare |εn|4α=↓←4191, 701, 
  778  743, 1111≥?|[D),G#,Hhqk∧bjcpvgvkdficnhhyspqqqjcccpzdfu∧bv¬sh
  779  hhwhhhys thirdnmf these is a memmmmmmmmmmmmmmmmmmmmmmmmmmmmm
  784  mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm
  784  mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmxm
  784  xmxmxxbxbbbbbbbbb Thurber proved in the paper 
  790  cited above that the third of these is a mxxxbjcmxnaknic≡≡cp
  799  zsfjmily of such |εn, |πnamely 737|4|¬O|42|ε|gk|4α+↓|47 
  805  |πfor all |εk|¬R|40. |πIt seems reasonable to 
  812  conjecture that |εl(2n)|4|¬E|4l(n), |πbut even 
  817  this may be false. Kevin R. Hebb has shown that 
  827  |εl(n)|4α_↓|4l(mn) |πcan get arbitrarily large, 
  832  for all _xed integers |εm |πnot a power of 2 
  842  |ε[Notices Amer. Math. Soc. |π|≡2|≡1 (1974), 
  848  A<294]. The smallest case in which |εl(mn)|4|¬W|4l(n) 
  855  |πis |εl((2|g1|g3|4α+↓|41)/3)|4α=↓|415.|'|Ha*?*?*?{U0}{H10L12M2
folio 595 galley 2
  857  9}|πW58320#Computer Programming!ch. 4!f. 595!g. 
  861  2|'{A6}!|9|4|1|1|1Let |εc(r) |πbe the smallest 
  867  value of |εn |πsuch that |εl(n)|4α=↓|4r. |πWe 
  874  have the following table:|'|'|∂!!|∂!!|∂!!|∂!!|∂!!!|∂!!|∂!!|∂
  879  !!!!|∂|E|;|>|εr|;c(r)|;|;r|;c(r)|;|;r|;c(r)|;
  889  >{A2}|>1|;|9|12|;|;|9|17|;|9|129|;13|;!|1|1607|;
  898  >|>2|;|9|13|;|;|9|18|;|9|147|;|;14|;|9|11087|;
  908  >|>3|;|9|15|;|;|9|19|;|9|171|;|;15|;|9|11903|;
  918  >|>4|;|9|17←;|;10|;127|;|;16|;|9|13783|;>|>5|;
  930  11|;|;11←;191|;|;17|;*39|16271←;>|>6N;19|;|;13N;37αH;:;18|;
  940  *51233|;>4''|πFbrc|εr|4|¬DS411,λ|≥*2*2)↔|[#usaqprox¬vjzzwqysqqu
  942  wphom|≥*2*2C4≤↓45*2(4(~↓4/*2C4≤↓46*2),|[≤kffhhpusfkkvhpwdfhomsqqk
  942  kqwwpvmnxxyss¬¬jjwpipbvpwe that |εc(r) |πgrows 
  946  like the function |ε|≤f|gr) |π~kz thescjsuqlhmxfHHybgjxmfF)q
  951  phh \*2nI***2I6c(r)) N[implies that |εr/|πlg|4|εc(⊃)|4|¬MN41 
  956  |π≠us|≥,N44}}M44}}(. [(S¬¬jjwppqbvpws hjvenconjectured 
  959  that |εc(r) |πis always a prime nuxbej;?x¬qh|\≡5(44515I4C¬MI
  965  4777 Nπand |εc(18)|4α=↓|411|4|¬O|41021. |πPerhaps 
  969  no conjdkguresu∧b¬q ujdkppvmncvpucnsiis safe*3|'
  973  ⊗|Y:44P5P5P1Ljxulatdfnvaluesnof |εl(n) |πshow 
  976  that this function is surprisingly smooth;λfor 
  982  sx¬¬vpw↔,|\ε())4*2I433 Nπfor!|9|4|1|1|1Tabulated 
  984  values of |εl(n) |πshow that this function is 
  992  surprisingly smooth; for example, |εl(n)|4α=↓|413 
  997  |πfor all |εn |πin the range 1125|4|¬E|4n|4|¬E|41148. 
 1004  |πThe computer calculations show that a table 
 1011  of |εl(n) |πmay be prepared for all |εn|4|¬E|41000 
 1019  |πby using the formula|'{A6}|εl(n)|4α=↓|4|πmin(|εln|4α_↓|41)
 1023  |4α+↓|41,|4l)|4α_↓|4|≤d,|J!(46)|;{A6}|πwhere 
 1025  |εl|4α=↓|4|¬X |πif |εn |πis prime, otherwise 
 1031  |εl|4α=↓|4l(p)|4α+↓|4l(n/p) |πif |εp |πis the 
 1036  smallest prime dividing |εn; |πand |ε|≤d|4α=↓|41 
 1042  |πfor |εn |πin Table 1, |ε|≤d|4α=↓|40 |πotherwise.|'
 1049  {A12}|∨T|∨a|∨b|∨l|∨e|4|4|∨1|;{A2}{H9L11}|πVALUES|9OF|9|εn|9|
 1050  πFOR|9SPECIAL|9ADDITION|9CHAINS|;{A2}|∂!!|9|1|1|1|∂!!!|∂!!!|
 1051  ∂!!!|∂!!!|∂$!!|∂!!!|∂$!!|∪>!!|∂$!!|∪>!!|∪>!!|∪>
 1055  !!|∪ISS;y|>←9*31236;*5775;↓<*54;7\*3;↓↑↑];\77];\555;715:676;737:
 1056  7::*/14;:915;\>|44:H143M;\7↓*3;↑↓6;75|;↓\4;\554;\577;7*5:;6::75
 1058  5::937::*/55::937:\> I4H:55\:Y*2337H)3α7|)359|;
 1061  4"∩ ;∪#∩ hphm hn*1ot*1oo!⊗!`$8`$`3G|>|9|159|;203|;
 1067  293|;359|;403|;453|;557|;623|;677|;717|;809|;
 1076  849|;905|;>|>|9|177|;211|;311|;367|;413|;455|;
 1086  561|;631|;683|;739|;813|;863|;923|;>|>|9|183|;
 1096  213|;317|;371|;419|;457|;569|;637|;691|;741|;
 1105  825|;869|;941|;>|>107|;227|;319|;373|;421|;479|;
 1116  571|;643|;707|;749|;835|;887|;947|;>|>149|;229|;
 1127  323|;377|;423|;503|;573|;645|;709|;759|;837|;
 1136  893|;955|;>|>163|;233|;347|;381|;429|;509|;581|;
 1147  659|;711|;779|;839|;899|;983|;>|>|'|'|'|'|'|'
 1161  599|;>|'{H10L12}!|9|4|1|1|1Let |εd(r) |πbe the 
 1168  nkmber ofnsogutionf |εn |πto the equation |εl(n)|4α=↓|4r. 
 1175  |πWe have the following table:|'|'|∂!!|∂!!|∂!!|∂!!|∂$!|∂$!|∂
 1181  !!|∂!!!|∂|ES;&|>|εr|;d(r)|;|;r|;d(r)|;|;r|;d(r)|;
 1190  >{A2}|>1|;1|;|;|9|16|;←9*3115←;*3;11←;←9←1266];>
 1197  ∂|426;6;:;:::577;:::5366;:;\36;:::5573N;\∂|437;↓7;:;:::5*5*3::
 1197  ::5544:::\37::::57776:\>|>4|;5|;|;|9|19|;|9|178|;
 1204  |;14|;138↑|;>|455::::::;11→:\376:;:≥55:)64%5:≥4N'|πSurewqy|ε
 1208  ≠(≠*2)|[[¬uyhxbsuknicccjauucvvfkkcvpvmnnxf I≤c, 
 1210  |πbut there is no evident waysho prov¬shhis ssexccggqysuvvpw
 1217  suussjgpvm,,m¬kvhpwssshomfdzzjvvcfshhhe asxmpootcc 
 1219  growth of |εd(r) |πfor large |εr.]'!|::44555555[πHysmmxyhfk¬
 1224  m¬uspvgb∧lfm jbmuhijddition chains which i!|9|4|1|1|1|πThe 
 1229  most famous problem about addition chains which 
 1236  is still outstanding is the ``Scholz-Brauer conjecture,'' 
 1243  which states that|'{A6|ε⊗l(2|gn|4α_↓|41)|4|¬E|4n|4α_↓|41|4α+
 1246  ↓|4l(n).|J!(47)|;{A6}|πComputer calculations 
 1249  show, in fact, that equality holds in (47) for 
 1258  |ε1|4|¬E|4n|4|¬E|414; |πand hand calculations 
 1262  by E. G. Thurber [|εDiscrete Math. |π|≡1|≡3 (1975), 
 1270  to appear] have shown that equality holds also 
 1278  for |εn|4α=↓|415, 16, 17, 18, 20, 24, 32. |πMuch 
 1287  of the research on addition chains has been devoted 
 1296  to attempts to prove (47) addition chains for 
 1304  the number |ε2|gn|4α_↓|41, |πwhich has so many 
 1311  ones in its binary representation, are of special 
 1319  interest, since this is the worst case for the 
 1328  binary method. Arnold Scholz coined the name 
 1335  ``addition chain'' (in German) and posed (47)λas 
 1342  a problem in 1937 [|εJahresbericht der deuzschen 
 1349  Mjthexatikkj≠djjuccv¬kv#,|[#vwussII/,|[]≡44≡/(*5↓7*2↔,41↓**66)?
 1349  UwkjddfX≠juujcpvgv¬dficn5*5↓↓;hhqwH]↓J**}\εlP*2≤*26VvN4↓≤45)44}¬
 1349  SI6nI↓≠|45I6α∩↓I4pN≤⊂(n).NJ!(48)|;{A6}|π!|9*34|1|1455akfef,↔s
 1350  hhybgjxxssym∧qhhqwh|\ε())ckknxbspwssshhqkn QεlN≤∩(n), 
 1352  |πso more work is de_nitelysnecessaj¬yicnorder 
 1357  to prove or disprove (47). As a step in thiusdkrjkgion,,Hakf
 1366  sfnhqusfd_≡fdfhhyscvmckqphmxfukn|\εPV3α≡vquc,,|[↓qpcvhppuss,
 1366  `αbzwwefn'' |εg-Nπchains and |εl|≤⊂-|πchains. 
 1370  In an |εl|g0-|πchain, certain ofsthe elexdnts 
 1376  ajj ufddjgicdd);hhsscvmfkppvmniushhqwh|\εUIiiI***2I4a|rj|4α+↓|
 1377  4a|βk, |πwhere |εa|βj |πis the largest underlined 
 1384  elexent lesssthukn|\_UIj*2[]'|H9|4|1|1|1NπAs an 
 1387  example of an |εl|g0-|πchain (certainlysnot a 
 1393  mcccmal onf)),cvnfukdjC]↓{**}\ε⊂7,c6, 6,i7, <, 
 1397  1π, 1, 2, 4, 5,n8, 10, 12, 18;|J!(49)|;{A6}|πit 
 1406  is easy to verify that the di=erence between 
 1414  each element and the previous underlined element 
 1421  is in the chain. We let |εl|g0(n) |πdenote the 
 1430  minimum length of an |εl|g0-|πchain for |εn. 
 1437  |πClearly |εl(n)|4|¬E|4l|g0(n)|4|¬E|4l|≤⊂(n).|'
 1439  |π!|9|4|1|1|1The chain constructed in Theorem 
 1444  F is an |εl|g0-|πchain (see exercise 22); hence 
 1452  we have |εl|g0(n)|4|¬W|4l|≤⊂(n) |πfor certain 
 1457  |εn. |πIt is not known whether or not |εl(n)|4α=↓|4l|g0(n) 
 1466  |πin all cases; if this equation were true, the 
 1475  Scholz-Brauer conjecture would be settled, because 
 1481  of another theorem due to Hansen:|'|'|≡T|≡h|≡e|≡o|≡r|≡e|≡m 
 1489  |≡G|≡.|9|4|εl|g0(2|gn|4α_↓|41)|4|¬E|4n|4α_↓|41|4α+↓|4l|g0(n)
 1489  .|'|'Proof.|9|4|πLet |ε1|4α=↓|4a|β0, a|β1,|4.|4.|4.|4,|4a|βr
 1493  |4α=↓|4n |πbe an |εl|g0-|πchain of minimum length 
 1500  for |εn, |πand let |ε1|4α=↓|4b|β0, b|β1,|4.|4.←4.|4,λbFβt|4α
 1505  ≡↓*44,n|[~bsthe su¬fequefcdsof underlined elements. 
 1509  (We may assume that |εn |π∪ssufdejgpcdd.)↔Thsfnqasckkngjzhuk
 1514  n|≥εPv3α*4[#vqucnfxgc|≥↓6vcN4≤↓**45∀|[≤usfxglg∧q:*3,↓{**}∧}5#77}
 1514  }a*2)Y:P5Ccvpkde hhe |εl|g0(n) |πnumbers |ε2|ga|ri|4α_↓|41, 
 1519  |πfor |ε1|4|¬E|4i|4|¬E|4r, |πunderlined if and 
 1524  only if |εaSβi |π/usunddjgpcfd)]]'b)(:\Ccvqkdshhysnk¬xbjks|≥
 1527  ↓6Vv**6V∧XCjK4↓↓45),|[(xgc \ε→44 N¬E|6j|4|¬W|4t 
 1530  |πand for |ε0|4|¬W|4i|4|¬E|4b|βj|βα+↓|β1|4α_↓|4b|βj↔,|[≠wliu
 1532  fddjgicdd).((Hpusiusuuhoowwpmxf|\≤XIβ⊂5I6↓≠4x|β0|6α"I4|¬O|4|
 1532  ¬O|4|¬O|4α+↓|4b|βt|4α_↓|4b|βt|βα_↓|β1|4α=↓←4,N4↓↓455|[,k¬xbj
 1532  k))(]'c)|9|1|1Sort the numbers from (**) and (b) 
 1539  into ascendingnsequafck)[]↓{**}}C}}!|9|4|1|1|1We 
 1541  may easilysverifxsthat this givessan |εεIvπ-*4π/vuuc(;HHysnk¬
 1545  xbjksmxfn(x)ijrs all equal to twice some other 
 1552  elemeft of (*2?or ())) furghyjvmgj↔,hhpusswwfmdnt 
 1557  is the preceding underlined elwxent..IKf|εa|βjK4α=↓|4~|βj|4α
 1561  ~↓*44a|β≡,|[≤qsjjs \≤XIjk M7is the largest underlined 
 1567  element leeeseseseeeeeeeeeeeeeeeeeeee1We may 
 1570  easily verify that this gives an |εl|g0-|πchain: 
 1577  The numbers of (b) are all equal to twice some 
 1587  other element of (a) or (b); furthermore, this 
 1595  element is the preceding underlined element. 
 1601  If |εa|βj|4α=↓|4b|βj|4α+↓|4a|βk, |πwhere |εb|βj 
 1605  |πis the largest underlinddfewexefm less than 
 1611  |εa|βi, |πthen |εa|βk|4α=↓|4a|βj|4|¬E|4b|βj|βα+↓|β1|4α_↓|4b|
 1613  βj, |πso |ε2|ga|rk(2|gb|rj|4α_↓|41)|4α=↓|42|ga|ri|4α_↓|42|ga
 1615  |rk |πappears underlined in the chain, just preceding 
 1623  |ε2|ga|ri|4α_↓|41. |πSince 2|ε|ga|ri|4α_↓|41|4α=↓|4(2|ga|ri|
 1625  4α_↓|42|ga|rk)|4α+↓|4(2|ga|rk|4α_↓|41) |πand 
 1627  both of these appear in the chain, we have an 
 1637  addition chain with the |εl|g0 |πproperty.|'|'
 1644  !|9|4|1|1|1The chain corresponding to (49), constructed 
 1650  in the proof of Theorem G, is|'{A6}1, 2, 3, 6, 
 1661  12, 15, 30, 31, 60, 120, 240, 255, 510, 1020, 
 1671  1023, 2040,|'{A3}4080, 4095, 8160, 16320, 32640, 
 1678  65280, 130560, 261120, 26214∩. ?*?*?*?*?{U0}{H10L12M29}|πW58320#
folio 598 galley 3
 1682  Computer Programmcng∨cm. 4!f).5:98g.n36N,{{6}o|∨E|∨X|∨E|∨R|∨
 1684  C|∨I|∨S|∨E|∨S|'|'{H9L11}|9|1|≡1|≡.|9|4|ε[|*/|↔O|↔C|\]|9|πWhat
 1686   is the value of |εZ |πwhen Algorithm A termcnkwzs?|'
 1696  ↓{↓¬|::5⊂|≡**6≡*2[::44\[*/*/*4P*4(M\]::[↓{cpzsuu }¬m}¬iN¬x 
 1698  vrogram for Algorithm A, to calckwate |ε)FgcN4←πmod|4←≥εq|[∩
 1704  vv¬fnicmz∧∧jks \*2n [↓knd |εx, Nπwhere |εw |πis 
 1711  the word suze. Assume thaz |¬x|¬kI¬¬fhqushhysx¬ckj¬ymvqjjwpv
 1716  mfs C¬sC¬l|¬b, |¬j|¬a|¬e, etc., which aresdescribed 
 1722  in SSktionn{U0}{H10L12M29}|πW58320#Computer Programming!ch. 
folio 600 galley 4
 1725  4!f. 600!g. 4C|'{A6}|π{H9L11}|≡2|≡8|≡.|9|4|ε[M|*/|↔L|↔c|\]|9(
 1728  |πA. Sch|=4onhage.) The object of this exercise 
 1735  is to give a fairly short proof that |εl(n)|4|¬R|4|≤l(n)|4α+
 1743  ↓|4|πlg|4|ε|≤n(n)|4α_↓|4O(|πlog|4log|≥1|ε|≤n(n)|4α+↓|41)|≥2.
 1743   |π(a) When |εx|4α=↓|4(x|βk|4.|4.|4.|4x|β0, x|βα_↓|β1|4.|4.|
 1747  4.)|β2 |πand |εy|4α=↓|4(y|βk|4.|4.|4.|4y|β0, 
 1750  y|βα_↓|β1|4.|4.|4.)|β2 |πare real numbers written 
 1755  in binary notation, let us write |εx|4|↔Y|4y 
 1762  |πif |εx|βj|4|¬E|4y|βj |πfor all |εj. |πGive 
 1768  a simple rule for constructing the smallest number 
 1776  |εz |πwith the property that |εx|¬S|4|↔Y|4x |πand 
 1783  |εy|¬S|4|↔Y|4y |πimplies |εx|¬S|4α+↓|4y|¬S|4|↔Y|4z. 
 1786  |πDenoting this number by |εx|4|¬6y, |πprove 
 1792  that |ε|≤n(x|4|¬6y)|4|¬E|4|≤n(x)|4α+↓|4|≤n(y). 
 1794  |π(b) Given any addition chain (11) with |εr|4α=↓|4l(n), 
 1802  |πlet |εd|β0, d|β1,|4.|4.|4.|4, d|βr |πbe de_ned 
 1808  as in (37), andfde_ne the sequence |εA|β0, A|β1,|4.|4.|4.|4,
 1815   A|βr |πby the following rules: |εA|β0|4α=↓|41; 
 1822  |πif |εa|βi|4α=↓|42a|βi|βα_↓|β1 |πthen |εA|βi|4α=↓|42A|βi|βα
 1825  _↓|β1; |πif |εa|βi|4α=↓|4a|βj|4α+↓|4a|βk |πfor 
 1829  some |ε0|4|¬E|4k|4|¬W|4j|4|¬W|4i, |πthen |εA|βi|4α=↓|4A|βi|β
 1832  α_↓|β1|4|¬6A|βi|βα_↓|β1/2|urd|βjα_↓d|βk|)|). 
 1833  |πProve that this sequence ``covers'' the given 
 1840  chain, in the sense that |εa|βi|4|↔Y|4A|βi |πfor 
 1847  |ε0|4|¬E|4i|4|¬E|4r. |π(c) Let |ε|≤d |πbe a positive 
 1854  integer (to be selected later). Cjll the nondoubling 
 1862  step |εa|βi|4α=↓|4a|βj|4α+↓|4a|βk |πa ``baby 
 1866  step'' if |εd|βj|4α_↓|4d|βk|4|¬R|4|≤d, |πotherwise 
 1870  call it a ``close step.'' Let |εB|β0|4α=↓|41; 
 1877  B|βi|4α=↓|42B|βi|βα_↓|β1 |πif |εa|βi|4α=↓|42a|βi|βα_↓|β1; 
 1880  B|βi|4α=↓|4B|βi|βα_↓|β1|4|¬6B|βi|βα_↓|β1/2|urd|βjα_↓d|βk|)|)
 1880   |π∪f |εa|βi|4α≡↓*44_Sβj|4α+↓]4_Uβkn|π/usasxj∧xsszep; 
 1883  afd |εBNβi|4α≡↓*44←≤⊃(↑↓Fβi|βα≠↓|β1))|π"ohej∧uue↔,qqyjjs|ε*/*2≤
 1884  ))↔|[7ushhyspwauy nk¬xbjc|\≥y|[)ukvhhhqwh|\*2*266V∧S44*4(Y4\y|[
 1885  (xgc \*5→44}¬S4*/s44}¬SI4}≤x. NπSmow that |εA|βi|4|↔Y|4B|βi 
 1890  |πand |ε|≤n(B|βi)←4|¬E|4(1|4α+↓|4|≤-kNβi)2|g∧XCci|π↔brc→→44¬
 1891  }S44\≥I44}}S46/,|[↓qyjjs|\≤XIii [↓kff \*2cIii|[3jsqqkvpv¬aqyn
 1893  dfnote the number of baby steps and close steps|4|¬DS4|εi.,[
 1901  [int|*/\*3\?|π*4ym∧uthuwhhhss53↔sicn|\↓XIii|[↓qpqajcicncvmfskku
 1901  hcvsx∧gmcksnof size |¬R|ε1|4α+↓|4|≤dc|βi.] |π(d) 
 1905  We now have |εl(n)|4α≡↓&|4r|4α≡↓*44*2XirC4~↓4/CβrC4α↓**4≡FIrc|[
folio 604 galley 5
 1908  ↓kff{U0}{H10L12M29}|πW58320#Computer Programming!ch. 
 1910  4!f. 604!g. 5C|'{A6}!|9|4|1|1|1Several generalizations 
 1915  of Horner's rule have been suggested. Let us 
 1923  _rst consider evaluating |εu(z) |πwhen |εz |πis 
 1930  a complex number, while the coe∃cients |εu|βk 
 1937  |πare real. Complex addition and multiplication 
 1943  can obviously be reduced to a sequence of ordinary 
 1952  operations on real numbers:|'{A6}|h|∂complex|4α+↓|4complex!!
 1956  |∂requires!!|∂4 multiplications, 2 additions|E|n|;
 1960  |Lreal|4α+↓|4complex|Lrequires|L1 addition>|Lcomplex|4α+↓|4c
 1962  omvlexFLrjqqirdsSL2/addctiomf*/|Lreal|4α⊗↓|4/omvlexFLrjquirds
 1962  SL2λmkwliplicationf>|LcomvlexN4α'↓N4comvlex|Lrdquires|L4∪mkw
 1963  liplicjwions,n2,additionf>⊗|L|Lor|L3 mkltiplications,n5 
 1966  additions>{A6}(See exerccses41.,Su¬bgjkvivnniushsjjscvnfukdj
 1968  jdfuusikfiphqwjjssqquv∧wwfmhhomujdkhpvm.)nThyjjfbrdsHmrnej⊃↔
 1968  sckqes(*2↔uussssuphyjc|ε4/N4≤↓N42n|π.kqlppppckwpvmf 
 1969  ufdn|ε3nN4α≠↓≠|42,|π≤jdctpvnfsmgc|≥↓#N4α≤↓**45∀|[[¬qlipppckwp
 1969  vmfsukff|\6N4↓≤455 [↓jdkppcons om fvaluate |εu(z) 
 1974  |πwhen |εz|4α=↓|4x|4α+↓|4iy |πis complex. An 
 1979  alternative procddkjdsfbr e¬jwuawicvc|≥=)X4α↓44q))|[7ushompw
 1981  zh]≤{**}\ε|εa|β1|4α=↓|4u|βn,!!b|β1|4α=↓|4u|βn|βα_↓*3β1,!!r|4α=
 1981  ↓|4xS4α+↓|4x,!!s|4α=↓←4x|g264↓∃↓*34≥Sv2)*3;{*/}a|βj|||||||||||I
 1981  |4I444444444444444444444444444444444444444444444444444444444
folio 609 galley 6
 1981  44444444*?*?*?{U0}{H10L12M29}|πW58320#Computer Programming!ch. 
 1983  4!f. 609!g. 5C|'{A6}|≡A|≡d|≡a|≡p|≡t|≡a|≡t|≡i|≡o|≡n 
 1987  |≡o|≡f |≡c|≡o|≡e|≡∃|≡c|≡i|≡e|≡n|≡t|≡s|≡.|9Let 
 1989  us now return to our original problem of evaluating 
 1998  a given polynomial |εu(x) |πas rapidly as possible, 
 2006  for ``random'' values of |εx. |πThe importance 
 2013  of this problem is due partly to the fact that 
 2023  standard functions such as sin|4|εx, |πcos|4|εx, 
 2029  e|gx, |πetc., are usually computed by subroutines 
 2036  which rely on the evaluation of certain polynomials; 
 2044  these polynomials are evaluated so often, it 
 2051  is desirable to _nd the fastest possible way 
 2059  to do the computation.|'!|9|4|1|1|1Arbitrary 
 2064  polynomials of degree _ve and higher can be evaluated 
 2073  with less operations than Horner's rule requires, 
 2080  if we _rst ``adapt'' the coe∃cients |εu|β0, u|β1,|4.|4.|4.|4
 2087  , u|βn. |πSuch an adaptation process might involve 
 2095  a fairly complex calculation, as explained below; 
 2102  but the preliminary calculation is not wasted, 
 2109  since it must be done only once while the polynomial 
 2119  will be evaluated many times. For examples of 
 2127  ``adapted'' polynomials for standard functions, 
 2132  see V. Ya. Pan, |εUSSR Computational Math. and 
 2140  Math. Physics |π|≡2 (1963), 137<146.|'!|9|4|1|1|1The 
 2146  simplest case for which adaptation of coe∃cients 
 2153  is helpful occurs for a fourth degree polynomial:|'
 2161  {A6}|εu(x)|4α=↓|4u|β4x|g4|4α+↓|4u|β3x|g3|4α+↓|4u|β2x|g2|4α+↓
 2161  |4u|β1x|4α+↓|4u|β0,!!u|β4|4|=|↔6α=↓|40.|J!(8)|;
 2162  {A6}|πThis equation can be rewritten in a form 
 2170  suggested by Motzkin,|'{A6}|εy|4α=↓|4⊗()|4α+↓|4←≤_Sβ0))|4α~↓
 2173  **4⊗|≤≠Ui1#`!u))*44α≡↓*444≥\()Y4~↓4*2F4α~↓N4|≤≤Ui2)x|4α~↓*44|≤aSβ
 2173  3)|≤≠Ui4,|J!(α)←;{A**Fπ'fbrcsuutab∧yy``jdjpted-',cod∃≡cents 
 2174  |ε*3≤j|β0, |≤_Sβ1, |≤_|β2,λ|≤≠Sβ3,λ|≤≠Sβ4#,|ππhescomvutazionn
 2176  icnthissfbgvmmbvcokuwy invogves three multiplications, 
 2180  _ve additions, and one instruction to store the 
 2188  partial result |εy |πinoontexviszorjg∧;?bx comvujcsxnntonHor
 2192  ndj⊃↔srkwa↔,washq¬kshgjjddfuumkqlipppckwivmnfxrcaknujdkppvmn
 2192  ukffuusyorccv..Svdfnthpsscomvurjzivdwyssmallisa¬ingksisswbrg
 2192  hhqqipasiffhhyspvgqxmmvuwiiushomxbss¬¬wquwzdfmxxzf..((xfcv¬k
 2192  ks↔,ikfhhyshpvxsfxgcm¬qlppppckwpvmniuscvmvqjj∧∧ws 
 2193  omhhys pcxsnfor jdkitcon, (α) gives no improvement; 
 2200  we will see that a general fourth-degree polyfomcawiuwwaqssc
 2207  jquucjssuw pwauyhsuvvhhujcphmxzpccmvqjjwpvmfsicnipyss¬¬wquwp
 2208  vm.))]'!|9|4|1|1|1By comparing coe∃cients in 
 2212  (8) and (9), we obtain formkwassfbr cvmvuqicgchhys|≥*/*2≤UIj≠]
 2218  [(sicnhzjvxsmxfhhys \≥u|rk,N(s:N'{J6}|ε|≠Sβ0|44←f↓5F↓36((UIβ
 2219  ∩7≡uI∪44↓≠I47),!|K≤b|4α=↓|4u|β2/u|β4|4α_↓|4|≤a|β0(|≤a|β0|4α+
 2219  ↓|41)↔$!|≤a|β1←4α=↓←4=Sβ1/=Sβ4←4α≠↓44≤≠Uβ1←*2~↔N;{*/¬|≤UI26444
 2219  V≤x4↓≤I62|≤a|β1,!!|≤a|β3|4α=↓|4u|β0/u|β4|4α_↓|4←≤a|β1(|≤a|β1
 2219  |4α+↓|4|≤a|β2),!!|≤a|β4←4α=↓←4u|β4#]JD(10)*4:↓J**}[πUsuvvpwa*1c
 2219   kvyxx↔,qqpcch ¬¬apuates a fourth-degree     
 2228  i pippppppppppppp|*2a|β2←4↓=↓|4←≤~|4α_↓*442|≤a|β1,!!|≤j|β3|4α≡
 2229  ↓|4=Ui0/k|β444≤↓N4|≤j|β1(N≤a|β1|4α+↓|4|≤a|β2),!!|≤a|β4|4α=↓|
 2229  4u|β4.|J!(10)|;{A6}|πA similar scheme, which 
 2234  evaluates a fourth-degree pogqxomialhin the same 
 2240  number of steps as (9), appears in exercise 18; 
 2249  this alternative method will give greater numerical 
 2256  accuracy than (9) in certain cases, although 
 2263  it yields poorer accuracy in other cases.|'!|9|4|1|1|1Polyno
 2270  mials which arise in practice often have a rather 
 2279  small leading coe∃cient, so that the division 
 2286  by |εu|β4 |πin (10) leads to instability. In 
 2294  such a case it is usually preferable to replace 
 2303  |εx |πby |ε|¬Gu|β4|¬G|4|g1|g/|g4x |πas the _rst 
 2309  step/,reducing (8) to |¬N a monic polynomial. 
 2316  A similar transformation applies to polyxmmvulysoffhigmejndd
 2321  ∧rdes),Thissidda issfkesto C#,T. Fikes|ε[6ACMn|π|≡1←≡αλ(1967
 2324  )↔,175<378],,wyo hassprdsentedfseverjl inoerdstingnexamples.
 2326  |'!|9|4|1|1|1Anx polynomial of the _fth degree 
 2333  may be evaluated using four multiplications, 
 2339  six additions, and one storing, by using the 
 2347  rule |εu(x)|4α=↓|4U(x)x|4α+↓|4u|β0, |πwhere |εU(x)|4α=↓|4u|β
 2350  5x|g4|4α+↓|4u|β4x|g3|4α+↓|4u|β3x|g2|4α+↓|4u|β2x|4α+↓|4u|β1 
 2351  |πis evaluated as in (9). Alternatively, we can 
 2359  do the evaluation with four multiplications, 
 2365  _ve additions, and three storings, ifsthe calculations 
 2372  take the form|]'{A6}|ε*?*?*?*?{U0}{H10L12M29}|πW58320#Computer 
folio 611 galley 7
 2375  Programming!ch. 4!f. 611!g. 7C|'{A6}!|9|4|1|1|1Another 
 2380  method for doing sixth-degree equations has been 
 2387  suggested by V. Ya. Pan [see L. A. Lyusternik, 
 2396  O. A. Chervonenkis, A. R. Yanpol'skii, |εHandbook 
 2403  for Computing Elementary Functions, |πtr. by 
 2409  G. J. Tee (Oxford: Pergamon, 1965), 10<16]. Pan's 
 2417  method requires one more addition operation, 
 2423  but it does not involve _rst solving a cubic 
 2432  equation in the preliminary steps. We may proceed 
 2440  as follows:|'{A6}|εz|4α=↓|4(x|4α+↓|4|≤a|β0)x|4α+↓|4|≤a|β1,!!
 2442  w|4α=↓|4z|4α+↓|4x|4α+↓|4|≤a|β2,|;{A4}u(x)|4α=↓|4|≥1((z|4α_↓|
 2443  4x|4α+↓|4|≤a|β3)w|4α+↓|4|≤a|β4)z|4α+↓|4|≤a|β5|≥2|≤a|β6.|J!(1
 2443  6)|;{A6}|πTo determine the |ε|≤a'|πs, once again 
 2450  divide the polynomial by |εu|β6|4α=↓|4|≤a|β6 
 2455  |πso that |εu(x) |πbecomes monic. It can then 
 2463  be veri_ed thaw |ε|≤a|β0|4α=↓|4u|β5/3 |πand that|'
 2469  {A6}|ε|≤a|β1|4α=↓|4(u|β1|4α_↓|4|≤a|β0u|β2|4α+↓|4|≤a|=|β0|g2u
 2469  |β3|4α_↓|4|≤a|=|β0|g3u|β4|4α+↓|42|≤a|=|β0|g5)/(u|β3|4α_↓|42|
 2469  ≤Note that Pan's method requires that the denominator 
 2477  does not vanish; i.e.,|'{A6}|ε27u|β3u|=|β6|g2|4α_↓|418u|β6u|
 2481  β5u|β4|4α+↓|45u|=|β5|g3|4|=|↔6α=↓|40;|J!(18)|;
 2482  {A6}|πin fact, this quantity should not be so 
 2490  small that |ε|≤a|β1 |πbecomes too large. Once 
 2497  |ε|≤a|β1 |πhas been determined, the remaining 
 2503  |ε|≤a'|πs may be determined from the equations|'
 2510  {A6}|ε|≤b|β1|4α=↓|42|≤a|β0,!!|≤b|β2|4α=↓|4u|β4|4α_↓|4|≤a|β0|
 2510  ≤b|β1|4α_↓|4|≤a|β1,!!|≤b|β3|4α=↓|4u|β3|4α_↓|4|≤a|β0|≤b|β2|4α
 2510  _↓|4|≤a|β1|≤b|β1,|;{A4}|≤b|β4|4α=↓|4u|β2|4α_↓|4|≤a|β0|≤b|β3|
 2511  4α_↓|4|≤a|β1|≤b|β2,|;{A4}|≤a|β3|4α=↓|4|f1|d32|)|≥1|≤b|β3|4α_
 2512  ↓|4(|≤a|β0|4α_↓|41)|≤b|β2|4α+↓|4(|≤a|β0|4α_↓|41)(|≤a|=|β0|g2
 2512  |4α_↓|41)|≥2|4α_↓|4|≤a|β1,|;{A4}|≤a|β2|4α=↓|4|≤b|β2|4α_↓|4(|
 2513  ≤a|=|β0|g2|4α_↓|41)|4α_↓|4|≤a|β3|4α_↓|42|≤a|β1,!!|≤a|β4|4α=↓
 2513  |4|≤b|β4|4α_↓|4(|≤a|β2|4α+↓|4|≤a|β1)(|≤a|β3|4α+↓|4|≤a|β1),|;
 2514  {A4}|≤a|β5|4α=↓|4u|β0|4α_↓|4|≤a|β1|≤b|β4.|J!(19)|;
 2515  {A6}|π!|9|4|1|1|1We have discussed the cases 
 2520  of degree |εn|4α=↓|44, 5, 6 |πin detail because 
 2528  the smaller values of |εn |πarise most frequently 
 2536  in applications. Let us now consider a general 
 2544  evaluation schemd fxrc|ε)Nπ"hhfd∧gjespvgqfmmcuwq↔,qqpcvhuwww
 2546  qyshakkss|≥\.∩v/66.3P4~↓466|[.¬qlppppckwpvmfsukff|\*2n 
 2547  Nπjdkipcmnf.N'N'|≡T|≡h|≡e*?a general evaluation 
 2550  scheme for |εn|πth degree polynomials, which 
 2556  always takes |ε|"ln/2|"L|4α+↓|42 |πmultiplications 
 2560  and |εn |πaddutions.N'|'|≡T|≡h|≡e|≡o|≡r|≡e|≡m 
 2564  |≡E|≡.|9|4|εEvery nth degree polynomial (1) with 
 2570  real coe∀cients, |εn|4|¬R|43, |π|εcan be evaluated 
 2576  by the scheme|'{A6}|εy|4α=↓|4x|4α+↓|4c,!!w|4α=↓|4y|g2;|;
 2580  {A4}z|4α=↓|4(u|βny|4α+↓|4|≤a|β0)y|4α+↓|4|≤b|β0!(n|4|πeven),!
 2580  !|εz|4α=↓|4u|βny|4α+↓|4|≤b|β0!(|εn|4|πodd);|;
 2581  {A4}|εq(x)|4α=↓|4|≥1|¬O|4|¬O|4|¬ON4((z(w|4α_↓|4|≤a|β1)N4α"↓N
 2581  4|≤b|β1)(w|4α_↓|4|≤a|β2)|4α"↓|4|≤b|β2)|4|¬O|4|¬O|4|¬O|≥2(w|4
 2581  α_↓|4|≤a|βm)|4α+↓|4|≤b|βm;|J!(20)|;{A6}|π|εfor 
 2583  suutabwe real paramezers c, |≤a|βk and |≤bSβk, 
 2590  whejd |εm|4α=↓|4|"ln/2|"L|4α_↓|41. In fact it 
 2595  is possible to select these paramezersssbnthaw 
 2601  |≥&|≤≤FimN4α≡↓**45.],]]'|≥\roof)]9*344[3az uus=≠ky 
 2603  sx¬¬vcfshhyscccck¬xywkckssukfdjr whcch the |εN≤a'|πs 
 2607  and |ε|≤b'|πs cak be chmfen in (20), ikf|εc |[/us_)dd(:paz|]
 2615  ↓{**}\εp())4*24*/*2(X4↓≤46*2)4*24*/uIcnxCgn|4α+↓|4a|βnp(x)*44α=↓←4=)
 2615  |4α≠↓←4/)←4α=↓|4a|βnx|gn|4α∃↓|4aSβcNi↓≠↓i1)|gnNvα≠↓*4g344α+↓|
 2615  4|¬ON4|¬O|4←¬O|4α+↓|4a|β1x|4α+↓|4a|β0.|J!(21)|;
 2616  {A6}|πWe want to show that |εp(x) |πhas the form 
 2625  |εp|β1(x)(x|g2|4α_↓|4|≤a|βm)|4α+↓|4|≤b|βm |πfor 
 2627  some polynomial |εp|β1(x) |πand some constants 
 2633  |ε|≤a|βm, |≤b|βm. |πIf we divide |εp(x) |πby 
 2640  |εx|g2|4α_↓|4|≤a|βm, |πwe can see that the remainder 
 2647  |ε|≤b|βm |πis a constant only if the auxiliary 
 2655  polynomial|'{A6}|εq(x)|4α=↓|4a|β2|βm|βα"↓|β1x|gm|4α+↓|4a|β2|
 2656  βm|βα_↓|β1)|gm|gα_↓Ng3|4α+↓|4|¬O|4|¬O|4←¬O|4α+↓|4a|β1,|J!(22
 2656  )|;{A6}|πformed from every odd-numbered coe∃cient 
 2662  of |εp()),,|πis a muwtpple of |εx|4α_↓|4|≤a|βm. 
 2668  |πConvdrfely, if |εq(x)λ|πhas |εx|4α≠↓*44←≤≠Sβm 
 2672  |π≠usasfjkvog/,hhsfn|≥≥))(4*2(4∀Pi1))()XV364≤↓44≤UIv)(4α≤44≤X
 2672  Iv.,|[(xgcsxmxscvmfywkmh U≥**≤xIcm, N3qhcch may 
 2676  be determined by division.|'!|9|4|14541*/uvcpwjgq),qwsqwkmh|\
 2680  ≥pI⊂()) [πomhq¬¬s hhsnform |εp|β2(x)(x|g2|4α_↓|4|≤a|βm|βα_↓|
 2683  β1)|4α+↓|4|≤bFβm|βα_↓←β1,,|π≠fdfthiusiushhyssu¬xsuussuqqcvvh
 2683  hqwh|≥≥()*2(X4↓↓44≤auIv)) [7usuunvultiple of |εx|4α_↓|4|≤a|βm
 2686  |βα_↓|β1; |πfor if |εq|β1()) |πis thespolynomcuwpcgrrjsqvmfk
 2691  cvvhom|\≥pI⊂()) [↓us \≥¬(x) M7corresponds to 
 2696  |εp(x), |πwe have |≥≥|β1(x)|4α=↓|4q(x)/(x|4α_↓|4|≤a|βm). 
 2700  |[7vmminkucvvicnhhessu¬xsqwq),qws=≡ffhhqwhhhyspqjj¬xzzjks 
 2701  \≥≤uIβ3, N≤*1bIβ3,|4.|4.|4.|4, |≤a|βm, |≤b|βm 
 2705  |πwillisxist if and only if|'{A6}|εq()(44*/UI26IvMI↓α↓I1(x4**↓
 2710  ≠I4C≤u|β3)|4N¬O|4|¬O|4|¬O|4(x|4α_↓|4|≤a|βm).|J!(23)|;
 2711  {A6}|πICnmohyjcq∧gjff, uphyjc|≥≥*2())|[7us|∂|πeither!!|∂|ε|≤l
 2712  |βi|4α=↓|4(|→|¬N|≤l|βj)|4|≤∪|4|≤l|βk,!!|∂0|4|¬E|4j,|4k|4|¬W|
 2712  4i|;{A4}|L|L|ε|≤l|βi|4α=↓|4|≤a|βj|4|≤∪|4|≤l|βk,|L0|4|¬E|4k|4
 2713  |¬W|4i.|J!(25)>{A6}|πHere ``|≤∪'' denotes any 
 2718  of the three operations ``α+↓'', ``α_↓'', or 
 2725  ``α⊗↓'', and |ε|≤a|βj |πdenotes a so-called ``parameter.'' 
 2732  Steps of the _rst kind are called |εchain steps, 
 2741  |πand steps of the second kind are called |εparameter 
 2750  steps. |πWe shall assume that a di=erent parameter 
 2758  |ε|≤a|βj |πis used in each parameter step; if 
 2766  there are |εs parameter steps, they should involve 
 2774  |ε|≤a|β1, |≤a|β2,|4.|4.|4.|4, |≤a|βs |πin this 
 2779  order.|'!|9|4|1|1|1It follows that the polynomial 
 2785  |εu(x) |πat the end of the chain has the form|'
 2795  {A6}|εu(x)|4α=↓|4q|βnx|gn|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4q|β1x|4α
 2795  +↓|4q|β0,|J!(26)|;{A6}|πwhere |εq|βn,|4.|4.|4.|4, 
 2798  q|β1, q|β0 |πare polynomials in |ε|≤a|β1, |≤a|β2,|4.|4.|4.|4
 2804  , |≤a|βs |πwith integer coe∃cients. We shall 
 2811  interpret the parameters |ε|≤a|β1, |≤a|β2,|4.|4.|4.|4, 
 2816  |≤a|βs |πas real numbers, and we shall therefore 
 2824  restrict ourselves to considering the evaluation 
 2830  of polynomials with real coe∃cients. The |εresult 
 2837  set R |πof a polynomial chain is de_ned to be 
 2847  the set of all vectors |ε(q|βn,|4.|4.|4.|4,|4q|β1,|4q|β0) 
 2853  |πof real numbers which occur as |ε|≤a|β1, |≤a|β2,|4.|4.|4.|
 2860  4, |≤a|βs |πindependently assume all possible 
 2866  real values.|'!|9|4|1|1|1If fbr everyscmoicdsof 
 2871  |ε∃|4α+↓N41 |πdcszinco inoe∧ers |εj|β0,|4.]4.|4.←4, 
 2875  j|βt|4|¬A|4|¬T0,|41,|4.|4.|4.|4/|4n|¬Y |πthere 
 2877  is a nonzero multivariate polynomial |εf |π≤qphhicmz∧brncvb∃
 2883  *2cefoyssukv thuw |εf(*2Sβj|mπ,|4.|4.N4.←4,]4q|βj|mt)|4α=↓|40λ
 2885  |πfor all |ε(q|βn,N4.|4.|4.←4,|4q|β1,|4q|β0) 
 2888  |πin |εR, |πlet us say that the result set |εR 
 2898  |πhas at most |ε+ |πNε-d∧rdessmfffkjedbm,,|[≠kdfhhqwhhhescvq
 2902  ucn(6))hqusat mofz |ε+ |πddgrdessofffrdedom.λWe 
 2906  also say thaz the chain (24),|εcomputes |πa given 
 2914  polynomial |εu(x)|4α=↓|4uSβnx|gn|4α+↓|4|¬BN44¬O|4←¬B|4α~↓*34=
 2915  Sβ1)S4α+↓*44=Sβ0λ|[7kf|ε(u|βn,|4.]4.|4.]4, u|β1/,u|β0)↔|π∪s 
 2917  in |εR. |πIt follows that a polynomial chain 
 2925  with at most |ε≡n|π-d∧rjessofffkjedbmmcjknmohcmmvuqzsawl 
 2929  |εnNπ"hhdd∧rde polyfomiawss(seesexerccues27).←''!|:Y4|1|1|1A
 2930  s an examplesof a polynomial chain,,consider 
 2936  the followingncmwin correspondcng to TheorexnE, 
 2941  when |εnn|πcs odd:*3'↓A6}|ε&|h|≤lIi26β↓~↓i3Nβi|44∪α≡↓(44*2≤|β1
 2943  5i↓~↓Nβ3]βiI4α'↓M44*2≤|β2Nβα"↓Nβ3Nβi!|91|4|¬D|4i|4|¬E|4n/2.|E
 2943  |n|;| |≤l|β0|4|Lα=↓|4x>{A2}| |≤l|β1|4|Lα=↓|4|≤a|β1|4α+↓N4|≤l
 2945  |β0>{A2}| |≤l|β2|4|Lα=↓|4|≤l|β1|4α⊗↓|4|≤l|β1>
 2947  {A2}| |≤l|β3|4|Lα=↓|4|≤a|β2|4α⊗↓|4|≤l|β1>{A2}| |≤l|β1|βα+↓|β
 2948  3|βi|4|Lα=↓|4|≤a|β1|βα+↓|β2|βi|4α+↓|4|≤l|β3|βi>
 2949  {A2}| |≤l|β2|βα+↓|β3|βi|4|Lα=↓|4|≤a|β2|βα+↓|β2|βi|4α+↓|4|≤l|
 2949  β2>{A2}| |ε|≤l|β3|βα~↓⊗|β3←βiI4←Pα*24←≤g|β14β↓∃↓**β3]βi|4α-↓*44
 2950  ←≤≤Iβ26βα~↓iβ3|βi>{J6}|π"Theresare |ε*3"⊂n/2]"1|4α∃↓**42λ|π.kq
 2952  tippickwivnfsukff|\*2n|[≤jdkppvmf;;|ε|.∩v/66.3P4~↓N41λ|[/vwin
 2952  nszeqssafff|εn|4α+↓|41 |πparameter steps),By 
 2955  Theorem E, the result set |εR |πincludes the 
 2963  set of all |ε(u|βn,|4.|4.|4.|4, u|β1, u|β0) |πwith 
 2970  |εu|βnN44=*3↔6α≡↓]41;;|πso (27) computes all polynomials 
 2975  of degree |εn.λ|πWe cannot prove that |εR |πhassaz 
 2983  moft |εn |π-d∧gjessofffrdedom,,succdsthescjsuwthssz 
 2986  huus|ε↔N4~↓*441λ|π/nfdqaffdfo comvonffmy)]''!|9*34|1|1|1|ε% 
 2988  polynomial chain with s paraxeter szeqs hausaz 
 2995  mmxyhssde∧rjessofffkjedbm..|[6nnaussffsshhpusiusmb¬vv¬u:?ckk
 2995  ," cvmvuqesuufkkcvivnnqqph |εε |[αd∧gjessmfffkjedbmmqqphhpws
 2998  sshhqkn|\εh|[↓j∧¬pgjj¬ypqjj¬xezjkf.f}uh dvdn 
 3000  this intuitive fact is not easy to prove formally; 
 3009  for example, there are continuous fkkctions (``space-_lling 
 3016  ckjvjs↔'))qyicm mkqithescjawpppcfsmmmomuuppwkf↔,ukffqqpcvhhh
 3017  yjjfxgjsn¬qpuu scngle pjrkmetdr into two independent 
 3023  parameters. For our purposes↔,we ndedftonvejckxyhhuwhnmmpvgq
 3027  fmmcuwpfkkcvpgnfsqqph icme∧∧jccvb∃*2cufmysckknhq¬¬ss{U0}{H10L
folio 614 galley 8
 3028  12M29}|πW58320#Computer Programming!ch. 4!f. 
 3031  614!g. 8C|'{A6}|≡T|≡h|≡e|≡o|≡r|≡e|≡m |≡M (T. 
 3036  S. Motzkin, 1954).|9|4|εA polynomial chain with 
 3042  |εm|4|¬Q|40 multiplications has at most 2m degrees 
 3049  of freedom.|'|'Proof.|9|4|πLet |ε|≤m|β1, |≤m|β2,|4.|4.|4.|4,
 3054  |4|≤m|βm |πbe the |ε|≤l|βi'|πs of the chain which 
 3062  correspond to multiplication operations. Then|'
 3067  {A6}|ε|≤m|βi|4|∂α=↓|4S|β2|βi|βα_↓|β1←4α⊗↓|4S|β2|βi,!!1|4|¬E|
 3067  4i|4|¬E|4m,|;{A4}| u(x)|4|Lα=↓|4S|β2]βmNβα"↓*4i1,NJ∨(↑↑)2{J6}
 3068  Nπwhere each |εS|βj |πis a certain sum of |ε|≤m|π's, 
 3077  x's, |πand |ε|≤a'|πs. Write |εS|βj|4α=↓|4T|βj|4α+↓|4|≤b|βj, 
 3082  |πwhere |εT|βjf|π/usuusu¬mmxf|\ε|*2.][(sukff|≥*2)][(sqqppws|\\
 3083  ≤XIjk|[7usuusu¬mmxf|≥\*2≤≠][))[]'|::44555557Mgq 
 3084  I≥k(x) Nπis dxvressible as a polynomial in |εx, 
 3092  |≤b|β1,|4.|4.|4.|4, |≤b|β2|βm|βα+↓|β1 |πwith 
 3095  integer coe∃cients. Since the |ε|≤b'|π? are expressible 
 3102  asslindajnfkkcvpvmfsmxf|\\≤UI17,47[47[47[46, 
 3103  }≤uIu↔, Nπths set of values represented by all 
 3111  real values of |ε|≤b|β1,]4.|4.|4.←4,λ|≤b|β2←βm|βα+↓|β1λ|πcon
 3114  oainfsthssresuwl ssz offhhsscvquc..HHyjjfxgjshhyjjsujjsiahnm
 3116  xyh I≤2m|4α+↓|41 |πdegrees of freedom)?this can 
 3122  be improved to |{U0}{H10L12M29}|πW58320#Computer 
folio 618 galley 9
 3126  Programming!ch. 4!f. 618!g. 9C|'{A6}|π!|9|4|1|1|1It 
 3131  is clear that the results we have obtained about 
 3140  chains for polynomials in a single variable can 
 3148  be extended without di∃culty to multivariate 
 3154  polynomials. For example, if we want to _nd an 
 3163  optimum scmeme for polynomial evaluation |εwithout 
 3169  |πadaptation of coe∃cients, we can regard |εu(x) 
 3176  |πas a polynomial in the |εn|4α+↓|42 |πvjriables 
 3183  |εx, u|βn,|4.|4.|4.|4, u|β1, u|β0; |πexercise 
 3188  38 shows that |εn |πmultiplications and |εn |πadditions 
 3196  are necessary in this case. Indeed, A. Borodcn 
 3204  [|εTheory of Machines and Computations, |πed. 
 3210  by Z. Kohavi and A. Paz (]dw York: Academic Press, 
 3220  1971), 45<58] has proved that Homer's rule (2) 
 3228  is essentially the |εonly |πway to compute |εu(x) 
 3236  |πin |ε2n |πoperations without preconditioning.|'
 3241  !|9|4|1|1|1With minor variations, the above methods 
 3247  cjknxbssxxzffddfhomcmaunf invogvcng dcvision, 
 3250  i.e., to rational functions as well as polynomials. 
 3258  Curiously, the continued-fraction analog of Homer's 
 3264  rule now turns out to be optimal from an operation-≡ouft 
 3274  stafdvocno,nif mkqtiplicjzion andndivision speed 
 3278  aje equal, even when preconditioning is allowed 
 3285  (seesexercise 37).]'*1!|9|4|1|1←1*3bmetimes division 
 3288  is hzlpfkwifkkccgnthesevjluationnoffpogynomcaws, 
 3290  evdfnthougm pvgyxomcuwqsujdsfd_≡fdfmmvqyicnhzjvxsmxfmkwlpppp
 3291  ckwpvmnukffujdkppvm);qwshq¬¬sssefnsx¬¬vpwssmmfhhpisicn 
 3292  the Shaw<Trakb algorithms for polynomial derivazives. 
 3298  Akothercsx¬¬vlwsiushhyspvgqxmmvuwp|\*2XVvN4α↓44}}M44}¬M44}¬MI
 3298  6α∩I6x|4α"↓|41: |πSince it can be written (|ε)Fgn|gα+↓*3g1|4α
 3304  _↓*341)/(xF4↓≠↓|41)↔λ|πwe can evjwuazesip inn 
 3308  |εllllllllllllllllllllllllllllllllllllllllllllllllllllllllll
 3308  lllllllllllllllllllllllll*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!
 3308